昨天弄好了 LRU，但 LRU 其實有個坑：
如果一個 Key 過去一年被讀了一百萬次，但剛好這幾分鐘沒被讀；另一個沒什麼價值的 Key 剛好被寫入又讀了一次。LRU 可能會把前者當成「比較久沒用」而淘汰掉。

為了解決這種「歷史訪問失真」，Redis 4.0 加了 LFU (Least Frequently Used，最少使用頻率)。今天來拆 LFU 的設計，再做一版簡化實作。

LFU 淘汰演算法怎麼想

LFU 看的是「誰真的常被用」。需要淘汰時，它會優先挑訪問次數比較少的 Key，而不是只看最後一次被碰到的時間。

LFU 的兩個維度

如果只記錄訪問次數，會產生另一個嚴重的問題：一個在過去非常熱門的 Key，如果現在再也不被訪問了，它的次數依然很高，將永遠不會被淘汰（這被稱為「快取污染」）。

所以 LFU 不能只做一個單純 counter，至少要有兩件事：

1. 次數累加（Increment）：每次訪問時，增加其訪問計數。
2. 衰減機制（Decay）：隨時間流逝，如果 Key 沒被訪問，其訪問計數應該自動減少（衰減）。

Redis 中的 LFU 近似設計

Redis 將每個 Key 的 LFU 資訊壓縮在 24 個 bits 的 lru 欄位中：

• 前 16 bits：記錄最後一次進行衰減的時間戳。
• 後 8 bits：記錄一個對數計數器（Logarithmic Counter），這是一個近似的訪問計數。每次訪問時，並非單純 counter++，而是根據當前數值，以一定的概率來遞增（數值越大，遞增機率越低），最大值上限為 255。

看到這裡我頭都痛了，這 bit 操作也塞得太滿了，為了省記憶體真的是無所不用其極，實作時還得小心位移操作別寫錯。

程式碼實作：LFU 淘汰

這次我在專案裡提供 AllKeys-LFU 與 Volatile-LFU 兩種淘汰策略。

1. 累加訪問次數

我們在 db.go 的 getEntryWithoutLock 讀取路徑中，每次訪問時增加其 accessCount：

func (db *DB) getEntryWithoutLock(key string) (*entry, bool) {
	// ...
	e.lastAccessTime = time.Now()
	e.accessCount++ // 累加訪問頻率
	return e, true
}

2. 選擇淘汰鍵

在 code/db/evict.go 中，我們實作了 LFU 篩選邏輯——遍歷資料庫，找出 accessCount（訪問頻率）最低的 Key 進行淘汰：

func (db *DB) selectKeyToEvict() string {
	var bestKey string

	switch db.evictPolicy {
	// ...
	case PolicyAllKeysLFU:
		var minCount int
		first := true
		for k, v := range db.data {
			// 尋找訪問次數 (accessCount) 最少的 Key
			if first || v.accessCount < minCount {
				minCount = v.accessCount
				bestKey = k
				first = false
			}
		}

	case PolicyVolatileLFU:
		var minCount int
		first := true
		for k, v := range db.data {
			if v.expireAt.IsZero() { continue } // 僅針對設有過期時間的 Key
			if first || v.accessCount < minCount {
				minCount = v.accessCount
				bestKey = k
				first = false
			}
		}
	}
	return bestKey
}

跑起來看看

我們來測試一下讀寫分離。這同樣需要兩個終端機。

主節點 (port 6379) 與從節點 (port 6380) 啟動並設定好 SLAVEOF 後：

# 終端機 1: 主節點
$ redis-cli -p 6379
> SET foo bar
# 預期回覆：OK

# 終端機 2: 從節點
$ redis-cli -p 6380
> GET foo
# 預期回覆："bar"

從節點馬上就能讀到主節點剛剛寫入的資料，讀寫分離驗證成功！

總結

今天把 LFU 為什麼能補 LRU 的短板整理了一輪，也在儲存引擎裡補上 AllKeys-LFU 與 Volatile-LFU。

明天進到最後階段，先挑戰主從複製（Replication）和 SYNC 協定，應該滿刺激的。